<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
<script>



// [leetcode]704 二分查找
var search = function(nums, target) {
    let left = 0
    let right = nums.length - 1
    let half
    while(left <= right) {
        index++
        half = Math.floor((right + left) / 2)
        if (nums[half] === target) return half
        if (nums[half] > target) {
            right = half - 1
        } else {
            left = half + 1
        }
    }

    return -1
};

console.log(search([-1,0,3,5,9,12], 12))




// [leetcode]278 第一个错误版本 (二分查找改)

// 输入：n = 5, bad = 4
// 输出：4
// 解释：
// 调用 isBadVersion(3) -> false 
// 调用 isBadVersion(5) -> true 
// 调用 isBadVersion(4) -> true
// 所以，4 是第一个错误的版本。
var bad
var solution = function() {
    function isBadVersion (version) {
        return version === bad
    }
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 1
        let right = n
        let half
        while (left <= right) {
            half = Math.floor((left + right) / 2)
            if (isBadVersion(half)) {
                right = half
            } else {
                left = half + 1
            }
        }
        return left
    }
}
bad = 4
solution(5) // 4


// [leetcode]35 搜索插入位置 (二分查找改)
// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
// 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

var searchInsert = function(nums, target) {
    let left = 0
    let right = nums.length - 1
    let half

    while(left <= right) {
        half = Math.floor((left + right) / 2)
        if (nums[half] === target) return half
        if (nums[half] > target) {
            right = half - 1
        } else {
            left = half + 1
        }
    }
    return left

}

let nums = [1,3,5,6]
let target = 5

console.log(searchInsert(nums, target))




</script>
</body>
</html>